import java.util.Arrays;

/**
 * author Zhaojl
 */
public class QksortTest {
    public static void main(String[] args) {
        int[] a = {1, 2, 8, 6, 7, 4, 5 ,3 ,9 ,0};
        System.out.println("原   数 组 为:"+Arrays.toString(a));
        quickSort(a);
        System.out.println("排序后的数组为:"+Arrays.toString(a));
    }

    public static void quickSort(int[] a) {
        if(a.length>0) {
            quickSort(a, 0 , a.length-1);
        }
    }

    /**
     *
     * @param a 数组a
     * @param low 基数，第一次以a[0]的值作为基数
     * @param high 最后一个
     */
    private static void quickSort(int[] a, int low, int high) {
        //1.递归出口
        if( low > high) {
            return;
        }
        //2. 存
        int i = low;
        int j = high;
        //3.key以左边第一个为基准
        int key = a[ low ];
        //4.完成一轮排序
        while( i< j) {
            //4.1 从右往左找到第一个小于基准的数
            while(i<j && a[j] > key){
                j--;
            }
            // 4.2 从左往右找到第一个大于基准的数
            while( i<j && a[i] <= key) {
                i++;
            }
            //4.3 如果i<j就说明他俩还未碰面，那么交换i与j所指向的元素的值
            if(i<j) {
                int p = a[i];//定义中间件，把a[i]这个大于基准的值先临时赋给它
                a[i] = a[j];//把a[j]这个小于基准的值赋给a[i]
                a[j] = p;//取出中间件里的值，完成一轮交换
            }
        }
        // 4.4，调整key的位置,i与j相遇后的下一个值即i+1是j的基数
        int q = a[i];
        a[i] = a[low];
        a[low] = q;
        //5, 对key左边的数快排
        quickSort(a, low, i-1 );
        //6, 对key右边的数快排
        quickSort(a, i+1, high);
    }

}
